Complexidade de tempo

Esta página ou se(c)ção precisa ser formatada para o padrão wiki. Por favor ajude a formatar esta página de acordo com as diretrizes estabelecidas. (Julho de 2011)

Em ciência da computação, a complexidade de tempo de um algoritmo quantifica a porção de tempo tomada por um algoritmo para rodar em função do tamanho da entrada do problema. A complexidade de tempo de um algoritmo é comumente expressada usando a notação big O, que suprime constantes multiplicativas e outros termos de menor ordem. Quando expressada dessa forma, a complexidade de tempo é descrita como assintótica, i.e., o tamanho da entrada tende ao infinito. Por exemplo, se o tempo requisitado por um algoritmo em todas as entradas de tamanho n é no máximo 5n³ + 3n, a assíntota da complexidade de tempo é O(n³).

Complexidade de tempo é comumente estimada pela contagem do número de operações elementares realizadas pelo algoritmo, onde a operação elementar toma a quantia fixa de tempo para realizar. A quantidade de tempo tomada e o número de operações elementares realizadas pelo algoritmo diferem no máximo de um fator constante.

Desde que o algoritmo deve tomar uma quantidade diferente de tempo mesmo dentro de entradas de mesmo tamanho, a medida mais comum de complexidade de tempo usada, o pior caso do algoritmo de complexidade de tempo, denotado T(n), é no máximo a quantidade de tempo usada numa entrada de tamanho n. A complexidade de tempo é classificada pela natureza da função T(n). Por exemplo, um algoritmo com T(n) = O(n) é chamado de algoritmo de tempo linear, e um algoritmo com T(n) = O(2ⁿ) é dito ser um algoritmo de tempo exponencial.